package org.chnxi.study.algorithm.horse;

import java.awt.*;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

/**
 * 马踏棋盘-使用回溯算法查找
 */
public class HorseChessboard {
    int[][] chessboard;//棋盘
    private int x; //棋盘的列数
    private int y; //棋盘的行数
    // 创建一个棋盘，标记棋盘各个位置是否访问过
    private boolean[] visited ;
    //使用一个属性，标记是否棋盘所有位置都被访问过了
    private boolean finished = false;

    public HorseChessboard(int cols , int rows){
        x = cols;
        y = rows;
        chessboard = new int[cols][rows];
        visited = new boolean[cols * rows];
    }

    public static void main(String[] args) {
        //设置棋盘大小
        int cols = 8;
        int rows = 8;
        //马儿的初始位置
        int startRow = 1;
        int startCol = 1;

        HorseChessboard hc = new HorseChessboard(cols ,rows);

        long start = System.currentTimeMillis();
        hc.traversalChessboard(startRow-1 , startCol-1 , 1);
        long end = System.currentTimeMillis();
        System.out.println("共耗时："+(end - start));
        //输出棋盘
        for (int[] r : hc.chessboard){
            //System.out.println(Arrays.toString(r));
            for (int n : r){
                System.out.printf("%3d" , n);
            }
            System.out.println();
        }

    }

    /**
     * 完成马踏棋盘的算法
     * @param row 当前在第几行，从0开始
     * @param col 当前在第几列，从0开始
     * @param step 当前是第几部，从1开始
     */
    public void traversalChessboard(int row , int col, int step){
        chessboard[row][col] = step;
        visited[row * x + col] = true; //标记该位置已经访问
        //获取当前位置的下一个位置的集合
        List<Point> nextPoints = next(new Point(col , row));
        //增加贪心算法的优化
        sort(nextPoints);
        //遍历ps
        while (!nextPoints.isEmpty()){
            Point p = nextPoints.remove(0); //取出下一个可以走的位置
            //判断该点是否访问过
            if(!visited[p.y * x + p.x]){//说明还诶有访问过
                traversalChessboard(p.y , p.x , step+1);
            }
        }

        //step < x*y的成立情况：
        //1. 棋盘还没有走完
        //2. 棋盘处于回溯过程
        if(step < x * y && !finished){
            chessboard[row][col] = 0;
            visited[row * x + col] = false;
        }else{
            finished = true;
        }
    }

    /**
     * 根据当前位置（curPoint），计算马儿还能走哪些位置，并放入到集合中，最多有8个点
     * @param curPoint 当前位置
     * @return 可以走的位置集合
     */
    public List<Point> next(Point curPoint){
        List<Point> result = new ArrayList<>();
        Point p1 = new Point();
        //表示马儿可以走左上
        if( (p1.x = curPoint.x -2) >= 0 && (p1.y = curPoint.y - 1) >=0 ){
            result.add(new Point(p1));
        }

        //表示马儿可以走上左
        if( (p1.x = curPoint.x -1) >= 0 && (p1.y = curPoint.y - 2) >=0 ){
            result.add(new Point(p1));
        }

        //表示马儿可以走上右
        if( (p1.x = curPoint.x + 1) < x && (p1.y = curPoint.y - 2) >=0 ){
            result.add(new Point(p1));
        }

        //表示马儿可以走右上
        if( (p1.x = curPoint.x + 2) < x && (p1.y = curPoint.y - 1) >= 0 ){
            result.add(new Point(p1));
        }

        //表示马儿可以走右下
        if( (p1.x = curPoint.x + 2) < x && (p1.y = curPoint.y + 1) < y ){
            result.add(new Point(p1));
        }

        //表示马儿可以走下右
        if( (p1.x = curPoint.x + 1) < x && (p1.y = curPoint.y + 2) < y ){
            result.add(new Point(p1));
        }

        //表示马儿可以走下左
        if( (p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < y ){
            result.add(new Point(p1));
        }

        //表示马儿可以走左下
        if( (p1.x = curPoint.x -2) >= 0 && (p1.y = curPoint.y + 1) < y ){
            result.add(new Point(p1));
        }

        return result;
    }

    /**
     * 根据当前这一步的所有的下一步选择位置，进行非递减排序
     * @param ps 当前位置
     */
    public void sort(List<Point> ps){
        ps.sort(new PointComparator(this));
    }

    class PointComparator implements Comparator<Point>{
        HorseChessboard hc ;

        public PointComparator(HorseChessboard hc){
            this.hc = hc;
        }

        @Override
        public int compare(Point o1, Point o2) {
            int count1 = hc.next(o1).size();
            int count2 = hc.next(o2).size();
            if(count1 < count2){
                return -1;
            }else if(count1 == count2){
                return 0;
            }else{
                return 1;
            }
        }
    }


}
